МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завдання
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=5Б , n2=3П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Коберник Тарас Богданович КІ-44:
Завдання відповідно варіанту задане в таблиці 1.
Таблиця 1 Завдання відповідно варіанту
Розміри матриць
К-сть
процесорів (Р)
Тип початкового
завантаження даних
Співвідношення часових параметрів
N1
N2
N3
120
110
120
8
Завантаження через 1 процесор
tU=10tS=4tP=6tZ=tW
Згідно з таблицею 1 отримаємо такі значення n1,n2,n3:
n1=3П – А = 120; n2=2І – Б = 110; n3=4Б – А = 120;
Отже маємо матрицю А(120*110) та матрицю В(110*120)
Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44, де «nb»- номер букви П.І.Б студента.
Коберник Тарас Богданович КІ-44:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
К
О
Б
Е
Р
Н
И
К
Т
А
Р
А
С
Б
О
Г
Д
А
Н
О
В
И
Ч
3
1
4
2
5
6
7
8
Отримаємо – БНОРАСГД
Для БНОРАСГД отримаємо 35, 134, 250, 93, 27, 82, 74,13. Даний набір чисел записуємо у стовпець і переводимо і двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
035 - 00100011 00100011
134 - 10000110 10000110
250 - 11111010 11011010
093 - 01011101 01001101
027 - 00011011 => 00010011
082 - 01010010 01010010
074 - 01001010 01001000
013 - 00001101 00001100
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує певну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять). 0809350
type=(0+8+0+9+3+5+0)=25 mod 3 + 1 = 2(через один процесор)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k = 7-кількість цифр в номері залікової книжки.
tU=(9 +1)tS=(3 +1)tP=(5 +1)tZ=(0+1)tW
tU=tW; tS=tw/10; tP=tw/4; tZ=tw/6;
Анотація
В даній курсовій роботі розроблена структура перемноження матриці на матрицю на заданій структурі, завантаження матриць відбувається через один процесор. Процесор через який завантажуються дані є основним і він може взаємодіяти одночасно з трьома процесорами. Виконано обчислення часу виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з варіантом. Розроблена функціональна схема для завантаження даних в процесори, обчислення і збору результатів.
Програма до курсової роботи була розроблена в середовищі Microsoft Visual Studio 2010 на мові С++ з використанням бібліотек MPI. В курсовій роботі наведено граф-схеми виконання алгоритму множення двох матриць.
Зміст
Вступ………………………………………………………………………...
